package P287.P142;

import P287.P142.ListNode;
import org.junit.Test;

/**
 * @Author DJ同学
 * @Date 2021/2/23 9:02
 * @Version 1.0
 * @Name 环形链表 II
 * @Problem https://leetcode-cn.com/problems/linked-list-cycle-ii/
 * @Idea 返回开始环的第一个节点
 * 参考：https://www.bilibili.com/video/BV1W5411L7AF?t=139
 * f=a+n(b+c) f=2(a+b)
 * a=(n-2)(b+c)+2c 关键：第一次相遇之后
 *
 */
public class Solution {
    
    @Test
    public void  test(){
        ListNode root = new ListNode(3); 
        root.next = new ListNode(2);
        root.next.next = new ListNode(0);
        root.next.next.next = new ListNode(-4);
        root.next.next.next.next = root.next;
        ListNode listNode = detectCycle(root);
    }


    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null)return null;
        ListNode fast = head;//走两步
        ListNode slow = head;//走一步
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            //第一次相遇
            if(fast==slow){
                ListNode slow2 = head;
                //肯定会再次相遇 因为 a=(n-2)(b+c)+2c
                while(slow2!=slow){
                    slow = slow.next;
                    slow2 = slow2.next;
                }
                return slow;
            }
        }
        return null;
    }
}
